import java.util.Stack;

public class Sorting {  // 都是从小到大排序
//    直接插入排序
//    适用于 待排序序列 基本有序      越有序 排序越快
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int t = array[i]; // 待插入的值
            int j = i - 1; // 表示已排好序区域的元素索引
            while (j >= 0) {
                if (t < array[j]) {
                    array[j + 1] = array[j]; // 将大于 t 的元素向后移动一位
                } else {
                    break; // 找到正确的位置，跳出循环
                }
                j--;
            }
            array[j + 1] = t; // 将 t 插入到正确的位置
        }
    }

//    希尔排序(缩小增量排序)  是插入排序的优化版
    public static void ShellSort(int[] array){
        int gap = array.length;
        while(gap > 1){ // 最后变成一组
            gap /= 2;   // gap表示间隔 步长
            Shell(array,gap);
        }
        Shell(array, 1); // 最后对整个数组进行一次gap为1的插入排序，以确保数组完全有序
    }

    public static void Shell(int[] array,int gap){
        for (int i = gap; i < array.length; i++) {
            int temp = array[i];
            int j = i - gap;
            while(j >= 0){
                if (array[j] > temp){
                    array[j + gap] = array[j];
                } else {
                    break;
                }
                j -= gap;
            }
            array[j + gap] = temp;
        }
    }


    //    冒泡排序
    public static void bubbleSort(int[] arr){
        for (int i = 0; i < arr.length-1; i++) {
            for (int j = 0; j < arr.length-1-i; j++) {
                if (arr[j] > arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

//    希尔排序是不稳定的排序
//    缩小增量到最后可以变成一组
    public static void shellsort1(int[] arr){
        int gap = arr.length;
        while(gap > 1){//直到最后变成一组
            gap /= 2;
            shell1(arr,gap);
        }
        shell1(arr,1);
    }
    public static void shell1(int[] arr,int gap){
        for (int i = gap; i < arr.length; i++) {
            int temp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > temp) { // 如果当前位置的元素大于temp，则需要将其后移
                arr[j + gap] = arr[j]; // 将元素向后移动gap步
                j -= gap;
            }
//            此时找到合适的位置插入temp
            arr[j + gap] = temp;
        }
    }

//    选择排序
    public static void selectSort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i; // 假设当前 i 是最小值的索引
            // 在未排序部分寻找最小值的索引
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // 更新最小值的索引
                }
            }

            // 因为最小值的位置一直在更新 所以循环结束才能知道最小值的位置.
            // 交换当前元素和找到的最小元素
            if (minIndex != i) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

//    双向快速排序
    public static void doubleSelectionSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int minIndex = left;
            int maxIndex =left;
            for (int i = left + 1; i <= right; i++) {
                if (arr[minIndex] > arr[i]){
                    minIndex = i;
                }
                if (arr[maxIndex] < arr[i]){
                    maxIndex = i;
                }
            }
//            循环结束 找到了一轮中最大与最小的元素了
            if (minIndex != left){
                int temp = arr[minIndex];
                arr[minIndex] = arr[left];
                arr[left] = temp;
            }
            // 需要重新检查 maxIndex，
            // 如果最开始位置就是最大元素位置 他会被最小元素位置给换走(默认从小往右,最开始位置是小元素)
            if (maxIndex == left) {
                maxIndex = minIndex;
            }
            // 交换最大值和当前右端
            if (maxIndex != right) {
                int temp = arr[maxIndex];
                arr[maxIndex] = arr[right];
                arr[right] = temp;
            }
//            缩小区间
            left++;
            right--;
        }
    }

//    创建大根堆
    private static void createHeap(int[] array){
        int n = array.length;
//        从最后一棵子树开始遍历
        for (int parent = (n - 1 - 1) / 2; parent >= 0; parent--) {
            siftDown(array,0,array.length);
        }
    }

    //    向下调整
    private static void siftDown(int[] array, int parent, int length) {
        int largest = parent;
        int leftChild = (2 * parent) + 1;
        int rightChild = (2 * parent) + 2;

        // 如果左子节点存在且大于父节点，则更新最大值
        if (leftChild < length && array[leftChild] > array[largest]) {
            largest = leftChild;
        }

        // 如果右子节点存在且大于当前最大值，则更新最大值
        if (rightChild < length && array[rightChild] > array[largest]) {
            largest = rightChild;
        }

        // 如果最大值不是父节点，则交换并递归调整子树
        if (largest != parent) {
            int temp = array[parent];
            array[parent] = array[largest];
            array[largest] = temp;
            // 递归调整子树
            siftDown(array, largest, length);
        }
    }


    //    堆排序
//    不稳定   时间复杂度为O(N * logN)
    public static void heapSort(int[] array){
//        创建大根堆
        createHeap(array);
        int end = array.length - 1;

        // 逐个将最大值移到数组末尾，并调整剩余部分的堆
        while (end > 0) {
            // 交换堆顶元素和末尾元素
            int temp = array[0];
            array[0] = array[end];
            array[end] = temp;

            // 调整堆
            siftDown(array, 0, end);

            // 缩小堆的范围
            end--;
        }
    }

//    快速排序
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array, int start, int end){
        if (start >= end){
            return;
        }
        int pivotIndex = partition(array,start,end); // 轴点 作为基准
//      从后往前找小于轴点的元素 然后交换 从前往后找大于轴点的元素然后交换

        quick(array,start,pivotIndex - 1);
        quick(array,pivotIndex + 1,end);
    }

    private static int partition(int[] array, int start, int end){
        int pivot = array[start];
        int left = start;
        int right = end;

        while (left < right) {
            // 从右向左找小于基准的元素
            while (left < right && array[right] >= pivot) {
                right--;
            }
            // 交换
            if (left < right) {
                array[left] = array[right];
                left++;
            }

            // 从左向右找大于基准的元素
            while (left < right && array[left] <= pivot) {
                left++;
            }
            // 交换
            if (left < right) {
                array[right] = array[left];
                right--;
            }
        }

        // 将基准元素放到最终位置
        array[left] = pivot;
        return left;
    }

    /*
    快排: 空间复杂度: O(log N)
          最坏空间复杂度: O(N) 单分支的树
            快速排序的空间复杂度主要来自递归调用的栈空间
         时间复杂度: O(N * logN)
         最坏时间复杂度: O(N * N)  逆序
         不稳定
    */
    public static void quickFunction(int[] array,int low,int high) {
        if (low >= high){
            return;
        }
        // 获取划分位置
        int piovtIndex = part(array,low,high);

        // 递归对左半部分进行快速排序
        quickFunction(array, low, piovtIndex - 1);
        // 递归对右半部分进行快速排序
        quickFunction(array, piovtIndex + 1, high);

    }

    private static int part(int[] array, int low, int high) {
        int piovt = array[low]; // 将第一个元素作为基准元素
        int start = low;
        int right = high;

        while(start < right){
            // 从右向左找第一个小于基准的元素
            while(start < right && array[right] >= piovt){
                right--;
            }

            // 找到后与基准交换
            if (start < right) {
                array[start] = array[right];
                start++;
            }

            // 从左向右找第一个大于基准的元素
            while(start < right && array[start] <= piovt){
                start++;
            }

            // 找到后与基准交换p
            if (start < right){
                array[right] = array[start];
                right--;
            }
        }
//        此处left 与 right 重合 将 piovt 放到合适的位置
        array[right] = piovt;

        return right; // 此处 重合 返回 start 与 right 都可以
    }


//    快速排序优化 减少递归的次数  降低树的高度
//    三数取中快排法


//    求中位数的下标
    private static int middleNum(int[] array,int left,int right){
        int mid = left + (right-left)/2;
        if (array[left] < array[mid]) {
            if (array[mid] < array[right]) {
                return mid; // left < mid < right
            } else if (array[left] < array[right]) {
                return right; // left < right <= mid
            } else {
                return left; // right <= left < mid
            }
        } else {
            if (array[left] < array[right]) {
                return left; // mid <= left < right
            } else if (array[mid] < array[right]) {
                return right; // mid < right <= left
            } else {
                return mid; // right <= mid <= left
            }
        }
    }


    private static int medianOfThreePartition(int[] array, int low, int high) {
        int midianIndex = middleNum(array,low,high);

//        将中位数放在第一个位置
        int temp = array[low];
        array[low] = array[midianIndex];
        array[midianIndex] = temp;

//        定义 中心轴点
        int pivot = array[low];
        int start = low + 1;
        int end = high;

        while (true) {
            // 从右向左找小于基准的元素
            while (start <= end && array[end] >= pivot) {
                end--;
            }
            // 从左向右找大于基准的元素
            while (start <= end && array[start] <= pivot) {
                start++;
            }
            if (start >= end) {
                break;
            }
            // 交换找到的两个元素
            temp = array[start];
            array[start] = array[end];
            array[end] = temp;
        }

        // 将基准值放回正确的位置
        temp = array[low];
        array[low] = array[end];
        array[end] = temp;

        return end;
    }

    public static void threeWayMedianQuickSort(int[] array, int low, int high) {
        if (low >= high){
            return;
        }

        int pivotIndex = medianOfThreePartition(array,low,high);

//        递归左右区间
        threeWayMedianQuickSort(array,low,pivotIndex - 1);
        threeWayMedianQuickSort(array,pivotIndex + 1,high);
    }

//    非递归实现快速排序 使用栈的方式
    public static void quickSortNonR(int[]array){
        int start = 0;
        int end = array.length-1;
        Stack<Integer> stack = new Stack<>();// 使用栈来存储需要处理的子数组边界

        // 初始分区操作
        int pivot = partition(array,start,end);

//        在快速排序中，数组被分为两部分：
//        一部分是所有小于基准值的元素，另一部分是所有大于基准值的元素。

        // 如果左子数组存在，将其边界推入栈中
        if (pivot > start+1){
            stack.push(start);
            stack.push(pivot-1);// 区间范围
        }

        // 如果右子数组存在，将其边界推入栈中
        if (pivot + 1 < end){
            stack.push(pivot+1); //区间范围
            stack.push(end);
        }

        // 循环处理栈中的子数组
        while (!stack.isEmpty()){
            end = stack.pop();
            start = stack.pop();
            pivot = partition(array,start,end); // 重新分区间
            if (pivot > start+1){
                stack.push(start);
                stack.push(pivot-1);
            }
            if (pivot + 1 < end){
                stack.push(pivot+1);
                stack.push(end);
            }
        }
    }

    public static void mergeSort(int[] array,int start,int end){
        if (start >= end){
            return;
        }

        int mid = start + (end - start) >> 1;

        // 递归排序左半部分
        mergeSort(array,start,mid);

        // 递归排序右半部分
        mergeSort(array,mid+1,end);

//        合并
        merge(array,start,mid,end);
    }

    private static void merge(int[] array, int left, int mid, int right){
        int start1 = left;// 左子数组的起始索引
        int start2 = mid + 1;
        int[] tempArr = new int[right - left + 1];
        int k = 0; // 临时数组的索引

//        合并两个有序子数组
        while(start1 <= mid && start2 <= right){
            if (array[start1] <= array[start2]){
                tempArr[k] = array[start1];
                start1++;
            } else {
                tempArr[k] = array[start2];
                start2++;
            }
            k++;
        }
//        走出循环 说明某一子数组为空了 直接将另一数组的剩下元素复制进临时数组
        
        // 复制剩余的左子数组元素
        while(start1 <= mid){
            tempArr[k] = array[start1];
            k++;
           start1++;
        }
        // 复制剩余的右子数组元素
        while(start2 <= right){
            tempArr[k] = array[start2];
            k++;
            start2++;
        }

//        将临时数组的元素 全部赋值回原元素
        for (int i = 0; i < tempArr.length; i++) {
            array[i + left] = tempArr[i];
        }
    }
}
